package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

/**
 * Created with IntelliJ IDEA.
 * 889. 根据前序和后序遍历构造二叉树
 *
 * @author liw
 * @version 1.0
 * @date 2022/7/5 9:21
 */
public class ConstructFromPrePost {

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        return find(preorder, 0, postorder.length - 1, postorder, 0, postorder.length - 1);
    }

    private TreeNode find(int[] as, int ast, int aend, int[] bs, int bst, int bend) {
        if (aend < ast) {
            return null;
        }
        TreeNode node = new TreeNode(as[ast]);
        if (aend == ast) {
            return node;
        }
        int f = bs[bend - 1];
        int index = ast;
        for (int i = ast; i <= aend; i++) {
            if (as[i] == f) {
                index = i;
                break;
            }
        }
        int c = index - ast - 1;
        node.left = find(as, ast + 1, index - 1, bs, bst, bst + c - 1);
        node.right = find(as, index, aend, bs, bst + c, bend - 1);
        return node;
    }

}
